package personal_exercise;

import java.util.*;

import model.TreeNode;

public class Demo2 {

    // 体操队形
    private static int res;
    private static boolean[] vis;
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        vis = new boolean[n + 1];
        int[] request = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            request[i] = in.nextInt();
        }

        dfs(n, 1, request);
        System.out.println(res);
    }
    private static void dfs(int n, int cur, int[] request) {
        if (cur > n) {
            res++;
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            int index = request[i];
            if (vis[index]) break;
            vis[i] = true;
            dfs(n, cur + 1, request);
            vis[i] = false;
        }
    }



    // NC6 二叉树中的最大路径和
    private static int ret;
    public static int maxPathSum (TreeNode root) {
        dfs(root);
        return ret;
    }
    private static int dfs(TreeNode root) {
        if (root == null) return 0;
        int leftValue = Math.max(0, dfs(root.left));
        int rightValue = Math.max(0, dfs(root.right));
        ret = Math.max(root.val + leftValue + rightValue, ret);
        return root.val + Math.max(leftValue, rightValue);
    }




    // 消减整数
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);

        int t = in.nextInt();
        while (t-- > 0) {
            int h = in.nextInt();
            int res = 0, a = 1;
            while (h > 0) {
                h -= a;
                if (h % (2 * a) == 0) {
                    a *= 2;
                }
                res++;
            }
            System.out.println(res);
        }
    }

    // 最长公共子序列的长度
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        String str1 = in.next(), str2 = in.next();
        char[] s1 = (" " + str1).toCharArray(), s2 = (" " + str2).toCharArray();

        // dp[i][j]: 字符串 s1 中 1 ~ i 的子串 与 字符串 s2 中 1 ~ j 的子串的最长公共子序列的长度
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }


    // NC164 最长上升子序列(二)
    public int LIS (int[] a) {
        int n = a.length;
        if (n <= 1) return n;

        List<Integer> list = new ArrayList<>();
        for (int x : a) {
            if (list.isEmpty() || x > list.get(list.size() - 1)) {
                list.add(x);
                continue;
            }

            int index = binarySearch(list, x);
            if (x < list.get(index)) list.set(index, x);
        }
        return list.size();
    }
    private int binarySearch(List<Integer> list, int x) {
        int left = 0, right = list.size() - 1, mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (list.get(mid) < x) left = mid + 1;
            else right = mid;
        }
        return left;
    }




    // 排序子序列
    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        int res = 0, cur = 0;
        while (cur < n) {
            if (cur == n - 1) {
                res++;
                break;
            }
            if (arr[cur] < arr[cur + 1]) {
                while (cur < n - 1 && arr[cur] <= arr[cur + 1]) cur++;
                res++;
            } else if (arr[cur] > arr[cur + 1]) {
                while (cur < n - 1 && arr[cur] >= arr[cur + 1]) cur++;
                res++;
            } else {
                while (cur < n - 1 && arr[cur] == arr[cur + 1]) cur++;
            }
            cur++;
        }
        System.out.println(res);
    }



    // 春游
    public static void main5(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            long n = in.nextLong(), a = in.nextLong(), b = in.nextLong();
            if (n <= 2) {
                System.out.println(Math.min(a, b));
                continue;
            }

            long res = 0;
            if (3 * a < 2 * b) {
                res += n / 2 * a;
                n %= 2;
            } else {
                res += n / 3 * b;
                n %= 3;
            }

            if (n != 0) {
                if (3 * a < 2 * b) {
                    res += Math.min(Math.min(a, b), b - a);
                } else {
                    if (n == 1) {
                        res += Math.min(Math.min(a, b), 2 * a - b);
                    } else {
                        res += Math.min(Math.min(a, b), 3 * a - b);
                    }
                }
            }
            System.out.println(res);
        }
    }



    // AB31 活动安排
    public static void main6(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = in.nextInt();
            arr[i][1] = in.nextInt();
        }

        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
        int res = 0, cur = 0;
        for (int i = 1; i < n; i++) {
            if (arr[cur][1] > arr[i][0]) {
                if (arr[i][1] <= arr[cur][1]) cur = i;
            } else {
                cur = i;
                res++;
            }
        }
        System.out.println(res + 1);
    }


    // 求和(dfs)
    private static StringBuilder path = new StringBuilder();

    public static void main7(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        dfs(1, n, m);
    }

    private static void dfs(int pos, int n, int target) {
        if (target == 0) {
            System.out.println(path);
            return;
        }
        if (path.length() > 0) path.append(' ');

        for (int i = pos; i <= n; i++) {
            if (target - i < 0) break;
            path.append((char)('0' + i));
            dfs(i + 1, n, target - i);
            path.deleteCharAt(path.length() - 1);
        }

        if (path.length() > 0) path.deleteCharAt(path.length() - 1);
    }


    // WY6 合唱团
    public static void main8(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();
        int k = in.nextInt(), d = in.nextInt();

        // f[i][j]:从前i个人中选j个人,且最后一个人必选,它们能力乘积的最大值
        // g[i][j]:从前i个人中选j个人,且最后一个人必选,它们能力乘积的最小值
        long[][] f = new long[n + 1][k + 1];
        long[][] g = new long[n + 1][k + 1];
        long INF = Long.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                f[i][j] = -INF;
                g[i][j] = INF;
            }
        }
        for (int i = 1; i <= n; i++) {
            f[i][1] = g[i][1] = arr[i - 1];
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= Math.min(i, k); j++) {
                for (int prev = Math.max(j - 1, i - d); prev < i; prev++) {
                    f[i][j] = Math.max(Math.max(f[prev][j - 1] * arr[i - 1], g[prev][j - 1] * arr[i - 1]) , f[i][j]);
                    g[i][j] = Math.min(Math.min(f[prev][j - 1] * arr[i - 1], g[prev][j - 1] * arr[i - 1]) , g[i][j]);
                }
            }

        }

        long res = -INF;
        for (int i = k; i <= n; i++) {
            res = Math.max(res, f[i][k]);
        }
        System.out.println(res);

    }



    // AB32 【模板】哈夫曼编码
    public static void main9(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.offer(in.nextLong());
        }

        long res = 0;
        while (pq.size() > 1) {
            long val1 = pq.poll(), val2 = pq.poll();
            res += val1 + val2;
            pq.offer(val2 + val1);
        }
        System.out.println(res);
    }


    // 435. 无重叠区间
    public static int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        if (n == 1) return 0;
        Arrays.sort(intervals, (a, b) -> a[0]- b[0]);

        int res = 0;
        int end = intervals[0][1];
        for (int i = 1; i < n; i++) {
            while (i < n && end > intervals[i][0]) {
                end = Math.min(end, intervals[i][1]);
                res++;
                i++;
            }
            if (i < n) end = intervals[i][1];
        }
        return res;
    }


    // LCR 074. 合并区间
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int n = intervals.length;
        if (n == 1) return intervals;
        List<int[]> res = new ArrayList<>();

        int start = 0, end = 0;
        for (int i = 0; i < n; ) {
            start = intervals[i][0]; end = intervals[i][1];
            while (i < n && end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);
                i++;
            }
            res.add(new int[]{start, end});
        }
        return res.toArray(new int[0][]);
    }


    // 游游的字母串
    public static void main10(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] arr = in.next().toCharArray();
        int n = arr.length;
        // dp[i][j]:以下标 i 结尾的子串全部变为 'a' + j 所需的最小操作次数
        int[][] dp = new int[n][26];
        for (int j = 0; j < 26; j++) {
            if (arr[0] - 'a' != j) dp[0][j] = Math.min(Math.abs(arr[0] - 'a' - j), 26 - Math.abs(arr[0] - 'a' - j));
        }

        for (int i = 1; i < n; i++) {
            for (char ch = 'a'; ch <= 'z'; ch++) {
                int j = ch - 'a';
                dp[i][j] = dp[i - 1][j];
                if (arr[i] != ch) dp[i][j] += Math.min(Math.abs(arr[i] - ch), 26 - Math.abs(arr[i] - ch));
            }
        }

        int res = Integer.MAX_VALUE;
        for (int j = 0; j < 26; j++) {
            res = Math.min(res, dp[n - 1][j]);
        }
        System.out.println(res);
    }


    // 天使果冻
    public static void main11(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();
        // 对数组进行预处理
        // dp[i]: 前 i 个果冻中,美味度第二大的值
        int first = arr[0], second = 0;
        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            if (arr[i] > first) {
                second = first;
                first = arr[i];
            } else if (arr[i] >= second) {
                second = arr[i];
            }
            dp[i] = second;
        }

        int q = in.nextInt();
        while (q-- > 0) {
            int x = in.nextInt();
            System.out.println(dp[x - 1]);
        }
    }
}
